﻿// 201 欧拉函数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
http://oj.daimayuan.top/course/21/problem/489

输入T，一共T组数据，每组一个数n，输出它的欧拉函数φ(n)。

输入格式
第一行一个数字T。

接下来T行，每行一个数字n。

输出格式
一共T行，每行一个数，表示这个数的欧拉函数φ(n)。

输入样例
2
12345
987654321
输出样例
6576
619703040
数据规模
对于100%
的数据，保证1≤T≤103,1≤n≤109。
*/

int phi(int x) {
	int res = x;
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) {
			res = res / i * (i - 1);
			while (x % i == 0) x /= i;
		}
	}

	if (x > 1) res = res / x * (x - 1);
	return res;
}


void solve() {
	int a; cin >> a;
	cout << phi(a) << endl;
}


int main()
{
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

 